from matplotlib import pyplot as plt
import matplotlib.patches as mpatches

import numpy as np

# Affichage de la table
def AfficheTable(L, g):
    sommets = list(g.keys())
    n = len(sommets)

    # Trouver le i max dans L
    i_max = max(k[0] for k in L.keys()) if L else 0

    # Créer une matrice RGB
    mat = np.zeros((i_max + 1, n, 3))

    for i in range(i_max + 1):
        for idx, v in enumerate(sommets):
            if (i, v) in L:
                mat[i][idx] = [0.2, 0.7, 0.3]  # Vert
            else:
                mat[i][idx] = [0.85, 0.85, 0.85]  # Gris clair

    plt.close('all')
    # Taille de figure plus généreuse
    fig, ax = plt.subplots(figsize=(max(6, n * 1.0), max(4, (i_max + 1) * 0.7)))
    ax.imshow(mat)

    # Afficher les valeurs dans chaque case
    for i in range(i_max + 1):
        for idx, v in enumerate(sommets):
            if (i, v) in L:
                valeur = L[(i, v)]
                if valeur == float('inf'):
                    txt = '∞'
                else:
                    txt = str(int(valeur))
                ax.text(idx, i, txt, ha='center', va='center',
                        color='white', fontsize=10, fontweight='bold')

    # Configurer les axes avec les noms des sommets
    ax.set_xticks(range(n))
    ax.set_xticklabels(sommets, fontsize=10, style='italic')
    ax.set_yticks(range(i_max + 1))
    ax.set_yticklabels(range(i_max + 1), fontsize=10)

    # Quadrillage
    ax.set_xticks(np.arange(-0.5, n, 1), minor=True)
    ax.set_yticks(np.arange(-0.5, i_max + 1, 1), minor=True)
    ax.grid(which='minor', color='black', linewidth=0.5)

    plt.xlabel('Sommets', fontsize=11)
    plt.ylabel('Nombre max. d\'arêtes (i)', fontsize=11)
    plt.title('Table de programmation dynamique', fontsize=12)

    # Ajuster les marges manuellement au lieu de tight_layout
    plt.subplots_adjust(left=0.15, right=0.95, top=0.9, bottom=0.15)
    plt.show()

# Graphe représenté par un dictionnaire d'adjacence
# graphe[u] = [(v1, poids1), (v2, poids2), ...]
graphe = {
    'S': [('U', 2), ('V', 4)],
    'U': [('V', -1), ('W', 2)],
    'V': [('W', 3), ('T', 4)],
    'W': [('T', 2)],
    'T': []
}
source = 'S'
L = {}  # Dictionnaire de mémoïsation